The present invention relates generally to a method for halftoning digital color images and is particularly directed to the use of interlocked threshold arrays or interlocked dot profiles. The invention is specifically disclosed in which images are rendered using a dither matrix representing correlated dot patterns, where the dots of each dot pattern are arranged to minimize a function of the variances in the number of dots per region across an appropriate range of region sizes, and in which each color plane threshold array is generated while considering the threshold arrays for all of the other color planes so as to become interlocked; or in which multiple threshold arrays are generated for a single color plane, but while each of these threshold arrays is generated, the other arrays for that color plane are considered so as to become interlocked.
Halftoning describes the process of displaying an image on a device which is capable of representing only a finite, discrete number of tone levels. The position and arrangement of the discrete picture elements should create the illusion of a continuous-tone image. Using the traditional halftoning techniques of clustered-dot ordered dither and dispersed-dot ordered dither, undesirable visual patterns often appear, caused by the fact that the dots are placed along a distinct, rectangular (or sometimes hexagonal) grid. For colored images, there is the additional disadvantage of moire patterns, resulting from the interaction of the spatial frequencies of the halftone patterns of the individual primary colors.
To overcome some of these difficulties, halftoning methods which incorporate randomness have been developed to eliminate the distinctly periodic patterns of ordered dither. In addition, colored images rendered with random dither are free of moire patterns. The earliest attempts to incorporate randomness used white noise, in which all spatial frequencies were represented equally. Although images rendered with white noise dither are free of periodic artifacts, the images nevertheless looked too grainy, which is caused by the presence of low spatial frequencies in the halftone pattern. If the low frequency or xe2x80x9cpink noisexe2x80x9d content of the signal is eliminated, the remaining xe2x80x9cblue noisexe2x80x9d retains only higher spatial frequencies. In a book titled Digital Halftoning, by R. A. Ulichney, it was disclosed that images rendered with blue noise dither possess sharp detail and are free of the visual artifacts of ordered dither.
Blue noise, or more generally, dispersed-dot stochastic halftoning offers superior visual quality. The earliest blue noise method, error diffusion, considers the quantization error in neighboring pixels when deciding how to quantize the current pixel. Other techniques incorporate models of the printing device""s physical behavior, or human visual perception, or a combination of both considerations. Examples of these other techniques include the minimum visual modulation approach described in an article titled Design of Minimum Visual Modulation Halftone Patterns, by J. Sullivan, L. Ray, and R. Miller; modified error diffusion, disclosed in an article titled Model-Based Halftoning, by T. N. Pappas and D. L. Neuhoff; least-squares model-based halftoning, disclosed in an article titled Least-Square Model-Based Halftoning, by T. N. Pappas and D. L. Neuhoff; and direct binary search, disclosed in an article titled Model-based Halftoning Using Direct Binarm Search, by M. Analoui and J. P. Allebach.
The minimum visual modulation approach described by Sullivan et al. builds a set of 256 binary images (one for each gray level) by optimizing each binary image according to a human visual modulation transfer function. The minimization technique of simulated annealing leads toward an optimal solution, however, the computational costs of each comparison is expensive, requiring a Fourier transform of each potential dot profile. The advantage is that, once this set has been generated, an image may be rendered quickly by simply matching each gray level to the appropriate binary image. The other conventional techniques offer better quality, but all rely upon image-dependent feedback, and require substantially more computation when rendering the image.
Halftoning using a dither array sacrifices some of the qualities of the image-dependent model-based approaches, but offers considerably greater speed when rendering the image. A dither array is a two-dimensional arrangement of numbers used to produce a halftone pattern. In typical applications, the numbers will be integers in the range from zero (0) through two hundred and fifty-five (255), inclusive. To produce a halftone pattern for a gray level xe2x80x9cgxe2x80x9d in the range of 0xe2x89xa6gxe2x89xa6255, every location in the dither array  less than g will be marked with a dot. Each resulting xe2x80x9cdot profilexe2x80x9d (i.e., a binary image representing a constant gray level) must necessarily be a subset of all darker dot profiles. Typically, a dither array is created one dot profile at a time.
It is usually impractical to create a dither array as large as the image which is to be rendered. Therefore, the dither array typically is xe2x80x9ctiled,xe2x80x9d or repeated periodically, as many times as needed to cover the image. Accordingly, the dither array must be free of any visual artifacts which would result in periodic patterns. The primary advantage of a dither array is its speed, which is due to the fact that for each pixel in the image, it is necessary to check only a single threshold value in the dither array.
An early dispersed-dot stochastic dither array was an adaptation of Sullivan""s ,minimum visual modulation approach. By imposing the additional constraint that the bit patterns be xe2x80x9ccorrelatedxe2x80x9d with one another, a dither array could be generated instead of using a set of 256 uncorrelated bit patterns (i.e., dot profiles). This conventional correlation approach was described in U.S. Pat. No. 5,214,517, by Sullivan et al.
A later patent, U.S. Pat. No. 5,111,310, by Parker et al. discloses the use of a blue noise mask. The Parker blue noise mask builds successive levels of the dither array by filtering the Fourier transform of each dot profile with a blue noise frequency distribution. The filtered dot profile is compared against the original dot profile to determine where dots should be added or removed, in order to create the next level (either higher or lower in gray scale level). Ulichney""s void-and-cluster algorithm, disclosed in an article titled The Void-And-Cluster Method for Dither Array Generation, by R. A. Ulichney provides a fast, simple algorithm for generating a blue noise dither array, based upon the spatial distances between the pixels in each dot profile. Although this method is quick, its quality falls short of the optimal solution. Improvements have been made to both the blue noise mask and the void-and-cluster algorithm, discussed in an article titled Modified Approach to the Construction of the Blue Noise Mask, by M. Yao and K. J. Parker, and a patent titled Halftone Images Using Special Filters, U.S. Pat. No. 5,317,418, by Qian Lin. Both of these conventional approaches are presently susceptible to local minima, as they are based upon greedy optimization techniques.
Stochastic screening combines the high quality of error diffusion with the high speed of screening by use of a threshold array. For color printing, stochastic screens may be used for each color plane. In some situations, each color plane must be rendered individually, without any knowledge of the other color planes. In one example, a xe2x80x9cdot-on-dotxe2x80x9d method uses the same threshold array for each color plane. Another example is a xe2x80x9cshiftingxe2x80x9d method which shifts the threshold array by a different offset distance for each color plane. Another method called xe2x80x9cfixed partitioningxe2x80x9d divides (i.e., partitions) the threshold range into xe2x80x9cNxe2x80x9d equally sized subranges, which are then used as the lightest set of subranges for each of the N planes.
When multiple color planes are combined together (i.e., superimposed or superpositioned), the individual stochastic screens should interact with each other so that the combination of dots from more than one plane should still produce a blue noise distribution. While any method of stochastic screening may be extended to color printing, the various methods used in the past each have their advantages and disadvantages. For example, the dot-on-dot method is sensitive to registration error and it fails to spread out the dots from multiple planes, which gives unnecessarily low spatial frequencies among the lighter tones. However, if dot placement is sufficiently consistent, and registration between color planes is sufficiently good, the dot-on-dot approach can also give reliable color consistency.
Another simple approach is to shift the threshold array by some horizontal and vertical offset for each of the color planes. Typically, the offsets for different planes will be mutually prime numbers (i.e., sharing no common divisors) to avoid the potential for periodic artifacts. The shifting method spreads out the dots for multiple color planes, but the resultant combination of dots contains too much white noise.
If there are only two color planes, the threshold array may be negated or inverted for the second color plane. For each threshold xe2x80x9ctxe2x80x9d in the original threshold array, the threshold at the same location in the second array will be the quantity xe2x80x9c255- txe2x80x9d (assuming that the threshold array values are in the range of 0-255). Thus, the lightest thresholds in one array will become the darkest thresholds in the negated array and vice versa. One color will use the original array and the other color will use the negated array, and the two colors will overlap one another only when there is more than 100% total coverage. In a paper titled, xe2x80x9cColor Halftoning With Blue Noise Masks,xe2x80x9d by M. Yao and K. G. Parker, the negating method is generalized for three or more color planes. For lighter shades, the negating method appears just as noisy as the shifting method. In general, the lightest thresholds tend to be located near the darkest thresholds in a given threshold array. In the negated array, the darkest thresholds will become the lightest thresholds. Thus, the lightest thresholds of the original array will tend to be located near the lightest thresholds in the negated array, and the pattern formed by the superposition of the two threshold arrays will appear noisy, at least in the lighter shades.
This problem will be most prominent when the lighter tones of individual color planes are combined together. For darker shades, the quality will steadily improve for two reasons: (1) the greater the separation between a threshold and its negated value, the less likely the two thresholds, together, form a pleasing pattern, although this aspect becomes least prominent for thresholds that are in the center of the intensity range; and (2) as more dots are added to the pattern, the spatial frequency increases, and the noise becomes more difficult to discern, although this aspect becomes least prominent when there is complete saturation.
As related above, both the shifting method and the negating method perform poorly for light shades, however, as the shades become darker, the negating method improves in quality compared to the shifting method. See U.S. Pat. No. 5, 341,228, by Parker and Mitsa for further information.
The above-referenced Yao and Parker article suggests that dividing the range of threshold values among each of the color planes could be utilized in a fixed partitioning scheme. While the fixed partitioning method does a better job than the shifting method for color combinations that are near 100% total coverage, for lighter shades the fixed partitioning method appears just as noisy as the shifting method.
All of the methods described above for stochastic screening in color allow for each color plane to be rendered independently of the other color planes. In some cases, this restriction facilitates the overall design. However, the lighter shades are generally too noisy when combining the color planes. It would be advantageous to provide a new method of color halftoning with stochastic screens in which each of the individual stochastic screens is designed so that all of the screens may fit together to produce a combined pattern of dots that has a blue noise distribution, thereby presenting a pleasing result when combining all of the color planes. It would also be advantageous to provide a new method of halftoning with non-stochastic screens, or a combination of stochastic and non-stochastic screens, in which each individual screen is designed such that all screens fit together to produce a combined pattern of dots that present a pleasing result when combining all color planes, or when placing adjacent screens of a single color plane in a tiling manner.
It would further be advantageous to provide a new method of halftoning using dot profiles without threshold arrays, in which the dot profiles of different color planes are interlocked so that they fit together to produce a combined pattern of dots that present a pleasing result when combining all color planes, or adjacent dot profiles of a single color plane. It also would be advantageous to provide a new method of halftoning using threshold arrays that are generated without the use of dot profiles, in which each individual array is designed such that all arrays fit together to produce a combined pattern of dots that present a pleasing result when combining all color planes, or when placing adjacent arrays (e.g., of different types) of a single color plane in a tiling manner.
Accordingly, it is a primary advantage of the present invention to eliminate visual patterns that arise from variations in dot density of dot profiles used in halftoning of digital images.
It is a further advantage of the present invention to reduce the xe2x80x9ccost function,xe2x80x9d which is the statistical variance of the dot density of dot profiles used in halftoning of digital images, thereby eliminating visual patterns while giving uniform density that does not contain objectionable visual artifacts.
It is another primary advantage of the present invention to provide xe2x80x9cinterlockedxe2x80x9dstochastic screens used in color halftoning so that the individual screens may fit together to produce a blue noise distribution of dots in the combined color pattern.
It is yet a further advantage of the present invention to provide interlocked stochastic screens used for color halftoning which can be used with as many individual color planes as desired, or which can be used with as few as two color planes.
It is still a further advantage of the present invention to provide a method of color halftoning that uses interlocked stochastic screens for each of the color planes in which each individual color plane produces a visually pleasing blue noise distribution, and in which the individual stochastic screens interact with one another so that the combination of dots from more than one plane still produces a visually pleasing blue noise distribution.
It is yet another advantage of the present invention to provide a method of color halftoning using stochastic screens to produce individual color planes that fit together to produce a combined pattern of dots that have a visually pleasing blue noise distribution, but that are not particularly sensitive to registration error.
It is still another advantage of the present invention to provide a method of halftoning using threshold arrays having dots/entries that fit together (i.e., interlocked) for a single color plane in which one of the multiple threshold arrays is a stochastic screen, and an adjacent of the threshold arrays is a non-stochastic screen, while producing a combined pattern of dots that have a visually pleasing blue noise distribution.
It is yet a further advantage of the present invention to provide a method of color halftoning using interlocked threshold arrays to produce individual color planes that fit together to produce a combined pattern of dots that have a visually pleasing blue noise distribution, in which dot profiles are not used to create the threshold arrays, and fuirther in which the tone levels may be generated in a non-sequential fashion.
It is still a further advantage of the present invention to provide a method of color halftoning using interlocked threshold arrays in which all gray levels, or large groups of gray levels, are generated simultaneously to avoid locally suboptimal solutions.
It is still another advantage of the present invention to provide a method of color halftoning using interlocked threshold arrays, or dot profiles without threshold arrays, in which the halftoning is provided for a printing device that is capable of rendering multiple tone levels, thereby requiring multi-level halftoning.
It is still a further advantage of the present invention to provide a method of color halftoning that uses interlocked threshold arrays that consider an additional decision criteria, such as a measure of the compressibility of the threshold arrays, or a criteria that involves mechanism dependencies, such as where the physical characteristics of the intended output device (i.e., a printer) might favor certain dot patterns over other dot patterns.
It is yet a further advantage of the present invention to provide a method of halftoning that uses interlocked threshold arrays for embedding a digital watermark, in which the placing of dots in one or more threshold arrays will encode the watermark.
Additional advantages and other novel features of the invention will be set forth in part in the description that follows and in part will become apparent to those skilled in the art upon examination of the following or may be learned with the practice of the invention.
To achieve the foregoing and other advantages, and in accordance with one aspect of the present invention, an improved method for generating a dispersed-dot stochastic dither array used in halftoning is provided using minimum density variance. By minimizing the variation in the distribution of dots in a given dot profile, a pleasing dot profile may be obtained. A dot profile array for a particular gray level is first created, and then a corresponding delta density sum array is created. At each location where the dot profile is equal to one (1), the delta density sum array is shifted so as to be centered at that location. The delta density sum array is added to an initially cleared cumulative density sum array for each location where the dot profile is equal to one (1). The available set of dot locations is then determined, and a pre-determined number of these dot locations is randomly selected as required to create the next gray level. If the next level to be created is an increase in gray level, then the available set of dot locations comprises those locations in the array that have no dot. If the next level to be created is a lower gray level, then the available set of dot locations comprises those locations that already contain a dot.
The randomly selected dot locations will have dots added if the next gray level is to be an increase, or those same randomly selected locations will have dots removed if the next level is to be a decrease in gray level. If increasing one gray level, the delta density sum array is shifted for each of the randomly selected positions to be centered at the randomly selected position, then added to the cumulative density sum array. If decreasing one gray level, the delta density sum array is shifted for each of the randomly selected positions to be centered at the randomly selected position, then subtracted from the cumulative density sum array. The final step is to minimize the variance of the density of the dot profile, using a technique known as xe2x80x9csimulated annealing.xe2x80x9d It will be understood that the xe2x80x9cnextxe2x80x9d gray level to be generated does not necessarily have to be a single level up or down.
Simulated annealing is used to find a dot profile which is nearly optimal with respect to a weighting function based upon the local density variances, and this may be extended to obtain a dither array. Each step of the simulated annealing exchanges the values at a previously selected location and a previously unselected available location in the dot profile. This movement of dots is repeated many times, during which process the variance of the density of the dot profile is calculated to see if each dot movement is an improvement or not. Improvement is part of the criteria for accepting the movement, thus as this iterative process is performed, the variance of the density will gradually decrease, until it has become sufficiently minimized. No Fourier transformations are required using the method of the present invention, and consequently, considerably less computation is needed as compared to some conventional methods.
For color printing, a separate threshold array is generated for each of the color planes. The method provided by the present invention interlocks the stochastic screens so that the threshold arrays are generated while considering the other color threshold arrays. Each individual threshold array is thereby xe2x80x9cinterlockedxe2x80x9d with the other threshold arrays, so that a blue noise distribution may be produced by the individual arrays as well as by any combination of the individual arrays. The interlocking method of the present invention applies to any algorithm for generating a stochastic screen, including the minimum density variance method, related above, the void and cluster algorithm, a frequency-based blue noise mask generation, and modeling based on the human visual modulation transfer function (MTF).
When generating a single threshold array using the method of the present invention, a particular criterion is used to determine where the next threshold value should be located. When using the minimum density variance method, the location is chosen so that the overall variance in the number of dots is minimized across a range of region sizes. For the void and cluster algorithm, the chosen location is either the largest void or largest cluster. For frequency-based methods, the location is chosen such that the frequency distribution of the new pattern matches a desired spectrum, such as blue noise or the human visual MTF.
The interlocking method of the present invention generates a set of threshold arrays simultaneously, and the selection of a threshold location in each array considers the criterion for all the threshold arrays being generated. For example, when using the void and cluster algorithm, the array location for a given threshold array will consider the locations of voids and clusters in all of the threshold arrays. This may reduce the quality of an individual array by a small amount, but it allows for the combination of the arrays to have a significantly better distribution. The simplest approach uses the average of the criteria for all threshold arrays. Although this simple approach tends to give better results for the combination of arrays, the quality of the individual arrays may be unacceptable.
Instead of treating each color plane separately, the interlocking method generates a combined set of threshold arrays. For each threshold value xe2x80x9ct,xe2x80x9d a set of locations will be chosen in each of the threshold arrays before progressing to the next threshold value. The selection of a location for threshold t in one array considers the criterion for all the threshold arrays. For example, with the minimum density variance method, the threshold location for a given array depends not only upon the dot density variance for its own dot pattern, but upon the dot density variance for the dot patterns of all the other threshold arrays as well. The threshold array location thereby could be chosen to minimize the average dot density variance for all of the threshold arrays, which may reduce the quality of an individual array by a small amount, but allows for the combination of the arrays to have a significantly better distribution.
To improve the quality of the individual arrays, the preferred method of the present invention uses a weighted average. When selecting a threshold location for an array xe2x80x9cixe2x80x9d using weighted averages, the criterion associated with array i may be assigned a greater weight than each of the other individual arrays"" criteria. For example, a threshold array""s own criterion could be weighted two (2) or three (3) times as much as the criterion for any other individual array. By using the interlocked stochastic screens approach, the overall visual affect will be improved for both individual threshold arrays and for a combination of more than one of the threshold arrays. The interlocked approach is clearly superior for lighter shades, given any number of color planes.
When generating threshold arrays for four-color (CMYK) printing, the yellow plane can often be excluded while generating the interlocked stochastic threshold arrays, since the yellow dots are so light that any artifacts in the yellow plane are extremely difficult to see. Therefore, black, magenta, and cyan are preferably assigned to each of three interlocked threshold arrays. Likewise, for three-color (CMY) printing, yellow can again be excluded while generating a set of two (2) interlocked threshold arrays. In this instance, an interlocked threshold array is generated for each of the colors magenta and cyan. In general, however, a set of xe2x80x9cPxe2x80x9d interlocked threshold arrays may be generated where there are at least N distinct color planes. In other words, a yellow plane can be included for either CMYK or CMY printing, resulting in a set of four (4) interlocked threshold arrays and three (3) interlocked threshold arrays, respectively.
If the color yellow is ignored, then the number of interlocked threshold arrays can be reduced, which also reduces constraints and that now allows better visual quality to be produced. Naturally, a yellow plane ultimately will need to be produced for color printing, however, it will not need to be interlocked with the threshold arrays of the other color planes. Therefore, the color plane can be generated by any method, which preferably will be the minimum density variance method, described hereinabove.
The quality of a set of three interlocked arrays visually looks even better when all three planes are combined, as compared to a combination on only two of the three planes. This should not be surprising, since the interlocked arrays are generated from a weighted set of criteria from all three planes. Even for darker shades, the interlocked arrays appear to offer quality comparable to fixed partitioning. The interlocking arrays method is thereby clearly superior to the previously known methods of generating color planes since it offers visually pleasing results at both light intensities and dark intensities.
When generating the set of xe2x80x9cPxe2x80x9d interlocked stochastic threshold arrays, one for each of xe2x80x9cPxe2x80x9d color planes, an array of P dot profiles DP[i] are used, each of a size Mxc3x97N. A variable named xe2x80x9cdotsneeded[i]xe2x80x9d is the number of dots needed for a dot profile DP[i] to reach the desired tone level. The method uses a variable xe2x80x9cCTN[i]xe2x80x9d which is initially set to zero (0) for all values of xe2x80x9ci.xe2x80x9d If the value for CTN[i] is less than the value xe2x80x9cdotsneeded[i]xe2x80x9d for a particular plane i, then a color plane i will be selected such that a number of xe2x80x9cnewdotsxe2x80x9d will be added to {or removed from} the dot profile DP[i], such that the number of xe2x80x9cnewdotsxe2x80x9d is at least one (1) and the quantity xe2x80x9cnewdots + CTN[i]xe2x80x9d does not exceed the value of the variable dotsneeded[i].
At this point, the value xe2x80x9cnewdotsxe2x80x9d is added to the quantity CTN[i]. Using a particular criterion to determine the physical array location of the xe2x80x9cnewdotsxe2x80x9d that are to be added to or subtracted from an individual stochastic threshold array, a function is performed which combines the criteria for all planes P. Once this function is performed to determine the proper locations to either add {or remove} the xe2x80x9cnewdotsxe2x80x9d, then the correct number of dots (i.e., the value of xe2x80x9cnewdotsxe2x80x9d) is added to {or removed from} the dot profile DP[i] for that plane i.
The locations in the threshold array for plane i are now marked such that these locations correspond to array locations at which dots were added to {or removed from} the dot profile DP[i]. The value of the variable CTN[i] is now evaluated again to see if it is less than the value xe2x80x9cdotsneeded[i].xe2x80x9d If the answer remains YES, then an additional amount of xe2x80x9cnewdotsxe2x80x9d will be added to {or removed from} this dot profile. If the result is NO, then this particular dot profile has been completed.
As related above, the criterion used to determine the location of the xe2x80x9cnewdotsxe2x80x9d for each individual stochastic threshold array can be any of a number of criteria known in the prior art, however, the preferred criterion is the minimum density variance method related hereinabove. Regardless of the precise criterion used, as long as the function combines all of the criteria for all of the planes xe2x80x9cP,xe2x80x9d then the individual threshold arrays will be interlocked, according to the principles of the present invention.
The principles of the present invention also apply to generating a set of interlocked dot profiles which do not use a threshold array for halftoning. While this would require more memory for a large number of gray levels, such interlocked dot profiles could be generated without regard to dot profiles that were previously generated for other gray levels, and the dot patterns can be perhaps improved as compared to using a threshold array. The removal of the constraints imposed by using threshold arrays are such that the dot patterns would not have to be correlated with previously or subsequently generated dot profiles, and a dot that had been placed at a certain coordinate location could later be removed, if desirable to create an improved image. This would be impossible when using threshold arrays.
In an opposite sense, the threshold arrays of the present invention can be generated without using dot profiles during the formative steps of the threshold array. More than one threshold array could be generated in this manner, and these threshold arrays could also be interlocked with respect to one another.
Other alternative methodologies with respect to the present invention include generating threshold arrays in which the tone levels are generated in a non-sequential fashion, and one example of this would be to use a binary sequence for generating the tone levels. Another alternative is to globally optimize the interlocked threshold arrays by simultaneously considering all tone levels for all threshold arrays being generated, and by doing so this could avoid locally suboptimal solutions.
If global optimization is not desirable, or not achievable due to hardware or processing time constraints, then a regional optimization could be used to generate interlocked threshold arrays, in which certain groups of gray levels are generated simultaneously to avoid certain locally suboptimal solutions. In one instance, the first group that may be generated could be for the lighter shades, which are often more important for proper development to provide pleasing visual effects of a printed output for a particular output printing device. Another optional methodology of regional optimization is to use a binary sequence while simultaneously generating certain gray levels at certain fixed points within the gray scale, and then later to generate the levels in between those already created.
Another alternative feature of the present invention is to generate multiple threshold arrays that are interlocked together for a single color plane. In one example, a set of two interlocked arrays can be used for a single color, in which one threshold array is a stochastic screen while the other threshold array is an ordered, clustered-dot screen. The stochastic screen could be used to render high frequency image content, while the other screen could be used to render low frequency image content, and depending upon the actual content of an area to be printed on a particular sheet of print media, one or the other of these threshold arrays would be used for that particular area of the page.
Another alternative feature of the present invention is to generate multiple threshold arrays that are interlocked together for multiple color planes. Such interlocked screens could be used to halftone a given tone level of a given color, and a decision criteria such as the local frequency content in the original image would select which screen (or weighted combination of screens) to use. Moreover, multiple threshold arrays, either for different color planes or for different tone levels in the same color plane, could be generated by using the methodology of the present invention in which all of the threshold arrays are of the same type, however, none of these would necessarily be stochastic arrays. For example, a set of interlocked threshold arrays could be generated as ordered, clustered-dot screens. In addition to striving for minimal overlap between color planes, the threshold arrays could be generated while considering the interaction between neighboring dots and the visual appearance when certain colors are printed atop one another.
Another feature that can be incorporated into the present invention is multi-level halftoning where the print output device is capable of rendering multiple tone levels. Where a printer is capable of printing a dark dot, a light dot, or no dot at all, there would be three possible output tone levels. This could occur for a color ink jet printer that uses both dilute inks and concentrated inks. Using the principles of the present invention, multiple dot profiles could be generated for each tone level in which the dot profiles are interlocked with respect to one another, and/or with respect to the other color planes or other tone levels of the same color plane. Furthermore, threshold arrays can be generated to take into account the multi-level halftoning for each tone level, and these threshold arrays can be interlocked with respect to one another, either along color planes, or along different tone levels of the same color plane. As noted above, it is possible to interlock together a single tone level across all of the colors while leaving the respective tone levels for a single color non-interlocked, if desired.
Yet another feature of the present invention is to create interlocked threshold arrays that obtain better data compression. In this circumstance, the decision criteria would include a measure of the compressibility of the threshold arrays. This would be quite useful in situations where two equally or almost equally desirable locations are found to place the next dot while generating the threshold arrays, and if one location might tend to produce more predictable dot patterns than the other location, this first location would tend to provide better data compression. While this approach may cause certain images to compress worse, the majority of images would benefit.
Still another feature of the present invention is to use interlocked threshold arrays to embed a digital watermark. Since digital images are subject to unauthorized reproduction, digital watermarks may be embedded within digital images, and such digital images would typically include digitally halftoned images. A secret message could be encoded using a xe2x80x9cT-out-of-Nxe2x80x9d threshold scheme, in which there are T xe2x80x9csharesxe2x80x9d of partial information, and in one methodology a duplicate set of interlocked threshold arrays is generated so that one set is commonly used to render the image, while the other set is used for detection. When rendering and printing the images produced by these two different threshold arrays, the printed outputs are superimposed and, if a watermark appears, then the printed image was a copy. An alternative methodology is to use a single threshold array that is split into two regions, and the original image is printed twice using the same set of interlocked threshold arrays in each case. The two images are superimposed upon one another, and as one image is shifted with respect to the other, the first region of the threshold array that contains the first share of the embedded watermark will become aligned with the second region of the threshold array containing the second share of the watermark. When that occurs the watermark will become visible. Of course, the watermark could be detected electronically rather than visually.
The embedded watermarks can be used for both monochrome halftoned images, or for color threshold arrays or for multi-level color threshold arrays. For example, a watermark could be designed for color images such that one share is encoded within the threshold array for a first color, while the other share is encoded in a threshold array for a different color.
Still other advantages of the present invention will become apparent to those skilled in this art from the following description and drawings wherein there is described and shown a preferred embodiment of this invention in one of the best modes contemplated for carrying out the invention. As will be realized, the invention is capable of other different embodiments, and its several details are capable of modification in various, obvious aspects all without departing from the invention. Accordingly, the drawings and descriptions will be regarded as illustrative in nature and not as restrictive.